package demo7;

/**
 * 两个字符串的最小ASCII删除和
 */
public class test7 {
    public int minimumDeleteSum(String s1, String s2) {
        // 创建dp表
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 初始化

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]  + s1.charAt(i - 1));
                }
            }
        }
        int sum = 0;
        for(char c : s1.toCharArray()){
            sum += c;
        }
        for(char c : s2.toCharArray()){
            sum += c;
        }
        return sum - dp[m][n]*2;
    }
}
